﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;


public class BishopMove
{

    public int howManyMoves(int r1, int c1, int r2, int c2)
    {
        if ((r1 + c1) % 2 != (r2 + c2) % 2) return -1;
        if (r1 == r2 && c1 == c2) return 0;
        if (Math.Abs(r1 - r2) == Math.Abs(c1 - c2)) return 1;
        return 2;
    }
}


public class BracketExpressions
{
    public string ifPossible(string expression)
    {
        if (RemovableExpression(expression)) return "possible";

        List<int> xPos = new List<int>();
        for (int i = 0; i < expression.Length; i++)
        {
            if (expression[i] == 'X') xPos.Add(i);
        }

        char[] brace = "()[]{}".ToCharArray();

        List<string> addBrace = "()[]{}".Select(e => e.ToString()).ToList();
        List<string> allBrace = addBrace;

        for (int i = 0; i < Math.Pow(6, xPos.Count); i++)
        {
            char[] charArray = expression.ToCharArray();
            for (int j = 0, d = 1; j < xPos.Count; j++, d *= 6)
            {
                int rc = ((int)(i / d) % 6);
                int pos = xPos[j];
                charArray[pos] = brace[rc];
            }
            if (RemovableExpression(string.Join("", charArray))) return "possible";
        }
        return "impossible";
    }

    private static bool RemovableExpression(string str)
    {
        while (true)
        {
            int lLen = str.Length;
            str = str.Replace("()", "");
            str = str.Replace("[]", "");
            str = str.Replace("{}", "");
            if (lLen == str.Length) break;
        }
        if (str.Length == 0) return true;
        return false;
    }
}

